(1) Field of the Invention
The present invention relates to a layout optimization problem solving method and program for use in solving a circuit layout optimization problem relating to optimum arrangement of circuits on, for example, a large-scale integrated (LSI) circuit; more commonly, to an element layout optimization problem relating to optimum arrangement of a plurality of elements (or elements to be arranged) in two or more dimensions, as well as to a computer-readable recording medium having the layout optimization problem solving program recorded thereon.
(2) Description of the Related Art
The element layout optimization problem is one relating to optimum arrangement, in a required space (or in a required area if the elements are two-dimensional), of a plurality of elements having a specified connection relationship. The problem is also called a graph mapping problem.
For example, if the optimum arrangement of individual circuits on the LSI circuit is determined, the LSI circuit can be made compact, and the length of wiring patterns used for interconnecting the circuits is minimized, thus enabling an improvement in wiring and the processing speed of the LSI circuit.
The element layout optimization problem can be solved by execution of an optimization problem solving algorithm (for example, a genetic algorithm, a min-cut method, an n-element exchange method, or a like method) to thereby determine the optimum layout of a plurality of elements in a required space, and by arranging the plurality of elements in the space on the basis of the determination.
If the element layout optimization is of large scale (that is, the number of elements to be optimally arranged is very large), the optimum layout of the elements is determined by taking the individual elements as points (or as the same shape) without consideration of size of the individual elements, in order to execute the optimization problem solving algorithm at high speed.
Since each of the elements has its own unique size, an overlap or clearance arises among elements even when the elements are arranged according to the thus-determined optimum layout, so that the arrangement of the elements is excessively loose or excessively dense.
In order to process the element layout optimization problem of large scale at high speed, an optimization problem solving algorithm is executed without consideration of size of the respective elements, and the resultant non-uniformity in density of the layout elements (layout unbalance) must be removed or reduced.
The present invention has been conceived to solve the foregoing problem, and the object of the present invention is to provide a layout optimization problem processing method which enables uniform arrangement of elements within space by reducing non-uniform arrangement in density of the elements, thereby processing an element layout optimization problem of large scale at high speed. Further, another object of the present invention is to provide a computer-readable recording medium on which is recorded a layout optimization problem processing program used for activating a computer to solve the element layout optimization problem.
To this end, the present invention provides a method of processing a layout optimization problem in which it is requested to find the optimal layout on a predetermined layout space for a plurality of elements that ought to be subjected to a predetermined connection relationship, comprising the steps of:
a first algorithm executing step of executing a genetic algorithm when information concerning the plurality of elements staying in an initial condition is available so that non-uniformity in density of the plurality of elements is reduced to bring the plurality of elements into a layout unbalance reduction halfway stage; and
a second algorithm executing step of executing a local layout unbalance reducing algorithm when information concerning the plurality of elements staying in the layout unbalance reduction halfway stage is available, whereby the non-uniformity in density of the plurality of elements staying in the layout unbalance reduction halfway stage is further reduced.
Here, the genetic algorithm can be executed in the first algorithm executing step by expressing the states of layout of the plurality of elements as genes; and by using, as a candidate solution for a problem of arranging the plurality of elements within the space, a chromosome which comprises a sequence of the genes and is defined as the space.
At the time of execution of the genetic algorithm, crossover can be carried out as a genetic operation in the first algorithm executing step by dividing the space, within which the plurality of elements are to be arranged, into a plurality of sub-divided spaces, thereby dividing the chromosome into a plurality of regions; and by exchanging at least one region selected from the plurality of regions in the chromosome with a counterpart portion in another chromosome.
Further, at the time of execution of the genetic algorithm, crossover can be carried out as a genetic operation in the first algorithm executing step by dividing the space, within which the plurality of elements are to be arranged, into a plurality of sub-divided spaces, thereby dividing the chromosome into a plurality of regions; and by pasting a specific region of the plurality of regions within the chromosome to a counterpart portion region of another chromosome if the specific region is found to have lower non-uniformity in density than that of the counterpart region.
At the time of execution of the genetic algorithm, mutation can be carried out as a genetic operation in the first algorithm executing step by dividing the space, within which the plurality of elements are to be arranged, into a plurality of sub-divided spaces, thereby dividing the chromosome into a plurality of regions; and by moving at least one of the plurality of elements within its respective regions.
Further, at the time of execution of the genetic algorithm, selection can be carried out as a genetic operation in the first algorithm executing step by use of a fitness function which enables a chromosome having lower non-uniformity in density of the plurality of elements to assume a great fitness value.
The present invention also provides a method of processing a layout optimization problem in which it is requested to find the optimal layout on a predetermined layout space for a plurality of elements that ought to be subjected to a predetermined connection relationship, comprising the steps of:
a first algorithm executing step of executing a genetic algorithm; and
a second algorithm executing step of executing a local layout unbalance reducing algorithm;
wherein the first algorithm executing step and the second algorithm executing step are combined to calculate the optimum value of a parameter utilized upon executing the local layout unbalance reducing algorithm, whereby non-uniformity in density of the plurality of elements staying in the initial layout is reduced.
In the first algorithm executing step, the parameter used for executing the local layout unbalance reducing algorithm can be expressed as a gene, and a chromosome comprising the sequence of the gene is used as a candidate solution for a problem of determining the parameter, thereby effecting the genetic algorithm.
In the second algorithm executing step, when the space within which the plurality of elements are arranged is divided into a plurality of sub-divided spaces, the parameter comprises information for specifying the sizes of the sub-divided spaces.
At this time, when the genetic algorithm is executed, a weighted average between genes of two parent chromosomes can be taken as a gene of a child chromosome in the first algorithm executing step, thereby effecting crossover as a genetic operation.
In the first algorithm executing step, when the genetic algorithm is executed, a portion of the chromosome may be pasted to a counterpart portion of another chromosome while the total sum of data for specifying the sizes of the sub-divided spaces included in the parameter is controlled so as to become unchanged, thereby executing crossover as a genetic operation.
Further, in the first algorithm executing step, when the genetic algorithm is executed, at least two genes of the chromosome are selected, and an arbitrary numerical value is added to the thus-selected genes so as not to change the total sum of data for specifying the size of the sub-divided space included in the parameter, thereby effecting mutation as a genetic operation.
In the first algorithm executing step, when the genetic algorithm is executed, selection can be effected as a genetic operation by use of a fitness function which enables a chromosome capable of reducing non-uniformity indensity of the plurality of elements to assume a high fitness value.
The layout optimization problem processing method is characterized in that, when the space within which the plurality of elements are arranged is divided into a plurality of sub-divided spaces, non-uniformity in density of the plurality of elements within each of the sub-divided spaces is reduced in the second algorithm executing step.
An algorithm to which a hydrodynamic analogy is applied can be used as the local layout unbalance reducing algorithm in the second algorithm executing step.
More specifically, the algorithm to which a hydrodynamic analogy is applied can be executed in the second algorithm executing step by moving at least one of the plurality of elements staying in the layout unbalance reduction halfway stage from a high-density location to a low-density location.
When the space within which the plurality of elements are to be arranged is divided into a plurality of sub-divided spaces, at least one of the plurality of elements included in each sub-divided space is moved from a high-density location to a low-density location within the sub-divided space in the second algorithm executing step.
Further, an algorithm to which a morphing analogy is applied can also be used as the local layout unbalance reducing algorithm in the second algorithm executing step.
More specifically, the algorithm to which a morphing analogy is applied can be executed in the second algorithm executing step by determining the center of morphing on the basis of the data regarding the plurality of elements staying in the layout unbalance reduction halfway stage, and by moving at least one of the plurality of elements to a location distant from the center of morphing.
When the space within which the plurality of elements are arranged is divided into a plurality of sub-divided spaces, determining the center of morphing for each of the sub-divided spaces and moving at least one of the plurality of elements included in each sub-divided space to a location distant from the center of morphing within the sub-divided space are carried out in the second algorithm executing step.
Further, the present invention provides a method of processing a layout optimization problem in which it is requested to find the optimal layout on a predetermined layout space for a plurality of elements that ought to be subjected to a predetermined connection relationship, comprising the steps of:
a first algorithm executing step of executing a genetic algorithm; and
a second algorithm executing step of executing a local layout unbalance reducing algorithm;
wherein the layout optimization problem is processed by reduction of non-uniformity in density of the plurality of elements staying in the initial layout.
More specifically, in the first algorithm executing step, the layout states of the plurality of elements are expressed as genes, and a chromosome which comprises a sequence of the genes and is defined as the space is used as a candidate solution for the problem of arranging the plurality of elements in the space, whereby the local layout unbalance reducing algorithm is executed in the second algorithm executing step during execution of the genetic algorithm.
Further, in the first algorithm executing step, the parameter used for executing the local layout unbalance reducing algorithm is expressed as a gene, and a chromosome comprising a sequence of the gene is used as a candidate solution for a problem of determining the parameter, whereby the local layout unbalance reducing algorithm is executed in the second algorithm executing step during execution of the genetic algorithm.
Further, in the first algorithm executing step, the parameter used for executing the local layout unbalance reducing algorithm is expressed as a gene; a chromosome comprising a sequence of the gene is used as a candidate solution for a problem of determining the parameter; the layout states of the plurality of elements are expressed as genes; and a chromosome which comprises a sequence of the genes and is defined as the space is used as a candidate solution for the problem of arranging the plurality of elements in the space, whereby the local layout unbalance reducing algorithm may be executed in the second algorithm executing step during execution of the genetic algorithm.
In the first algorithm executing step, the layout states of the plurality of elements are expressed as genes; a chromosome which comprises a sequence of the genes and is defined as the space is used as a candidate solution for the problem of arranging the plurality of elements within the space; the parameter used for executing the local layout unbalance reducing algorithm is expressed as a gene; and a chromosome comprising a sequence of the gene is used as a candidate solution for a problem of determining the parameter, whereby the local layout unbalance reducing algorithm may be executed in the second algorithm executing step during execution of the genetic algorithm.
The present invention also provides a computer-readable recording medium on which is recorded a layout optimization problem processing program for causing a computer to process a layout optimization problem in which it is requested to find the optimal layout on a predetermined layout space for a plurality of elements that ought to be subjected to a predetermined connection relationship, wherein the program causes the computer to act as:
first algorithm execution means for executing a genetic algorithm when information concerning the plurality of elements staying in an initial condition is available so that non-uniformity in density of the plurality of elements is reduced to bring the plurality of elements into a layout unbalance reduction halfway stage; and
second algorithm execution means for executing a local layout unbalance reducing algorithm when information concerning the plurality of elements staying in the layout unbalance reduction halfway stage is available, whereby the non-uniformity in density of the plurality of elements staying in the layout unbalance reduction halfway stage is further reduced.
Further, the present invention provides a computer-readable recording medium on which is recorded a layout optimization problem processing program for causing a computer to process a layout optimization problem in which it is requested to find the optimal layout on a predetermined layout space for a plurality of elements that ought to be subjected to a predetermined connection relationship, wherein the program causes the computer to act as:
first algorithm execution means for executing a genetic algorithm; and
second algorithm execution means for executing a local layout unbalance reducing algorithm;
wherein the first algorithm execution means and the second algorithm execution means are combined to calculate the optimum value of a parameter utilized upon executing the local layout unbalance reducing algorithm, whereby non-uniformity in density of the plurality of elements staying in the initial layout is reduced.
The present invention also provides a computer-readable recording medium on which is recorded a layout optimization problem processing program for causing a computer to process a layout optimization problem in which it is requested to find the optimal layout on a predetermined layout space for a plurality of elements that ought to be subjected to a predetermined connection relationship, wherein the program causes the computer to act as:
first algorithm execution means for executing a genetic algorithm; and
second algorithm execution means for executing a local layout unbalance reducing algorithm.
Accordingly, by means of the foregoing configuration, at the time of arrangement of a plurality of elements having a specified connection relationship within a required space, the layout optimization problem processing method comprises a first algorithm executing step for executing a genetic algorithm, and a second algorithm executing step for executing a local layout unbalance reducing algorithm. Therefore, there is yielded an advantage of an ability to quickly reduce non-uniformity in density of elements even at the time of processing of a layout optimization problem of large scale.
In the second algorithm executing step, at least one of the plurality of elements can be moved while the proximal relationship among the plurality of elements is conserved.
Further, in the second algorithm executing step, at least one of the plurality of elements can also be moved while the relative positional relationship among the plurality of elements is conserved.
Thus, in the second algorithm executing step, at least one of the plurality of elements can be moved while the proximal relationship among the plurality of elements or the relative positional relationship among the plurality of elements is conserved. Therefore, the range of layout optimization problems capable of being solved can be enlarged.
In the second algorithm executing step, when at least one of the plurality of elements is moved from the center of morphing to a distant location, the distance between the center of morphing and the element to be moved can be linearly enlarged.
Further, in the second algorithm executing step, when at least one of the plurality of elements is moved from the center of morphing to a distant location, the distance between the center of morphing and the element to be moved can also be non-linearly enlarged.
Thus, in the second algorithm executing step, the distance between the center of morphing and the element to be moved can be linearly or non-linearly enlarged, thereby enabling an enlargement of the range of layout optimization problems capable of being solved.
In the second algorithm executing step, elements to be subjected to reduction of non-uniformity in density can also be sequentially added when non-uniformity in density of the plurality of elements staying in the layout unbalance reduction halfway stage is reduced.
If a stationary element which cannot be moved exists among the plurality of elements, the stationary element is read as an element capable of undergoing reduction of non-uniformity in density in the second algorithm executing step, and non-uniformity in density of the plurality of elements staying in the layout unbalance reduction halfway stage can be reduced.
If a large element accounting for a larger proportion of the space than any of the other elements exists among the plurality of elements, the distance over which the large element is moved is reduced in the second algorithm executing step, and non-uniformity in density of the plurality of elements staying in the layout unbalance reduction halfway stage is reduced.
In the second algorithm executing step, the elements to be moved can be simultaneously moved at the time of reduction of non-uniformity in density of the plurality of elements staying in the layout unbalance reduction halfway stage.
In the second algorithm executing step, the elements to be moved can be moved gradually at the time of reduction of non-uniformity in density of the plurality of elements staying in the layout unbalance reduction halfway stage.
Therefore, by means of the foregoing configuration, in the second algorithm executing step, elements to be subjected to reduction of non-uniformity in density can be sequentially added; the stationary element can be read as an element to undergo reduction of non-uniformity in density; the distance over which the large element is moved can be reduced; the elements to be moved can be moved simultaneously; and the elements to be moved can be moved gradually. Therefore, the range of layout optimization problems capable of being solved can be further enlarged.
Further, a first island and a second island may be used in the first algorithm executing step; the first island comprising at least one chromosome group (population); the chromosome group including a plurality of sub-divided regions formed by vertically dividing the space within which the plurality of elements are arranged; the second island comprising at least one chromosome group (population); and the chromosome group including a plurality of sub-divided regions formed by horizontally dividing the space within which the plurality of elements are arranged.
At this time, the chromosome pertaining to the first island and the chromosome pertaining to the second island may be subjected to a genetic operation, i.e., crossover, in the first algorithm executing step, at the time of execution of the genetic algorithm; by application of the local layout unbalance reducing algorithm to the chromosome pertaining to the first island and to the chromosome pertaining to the second island to thereby move specific elements within the respective regions of the chromosomes; and by moving the specific elements within the respective chromosomes according to the sum of vectors relating to the distances over which the specific element pertaining to the first island and the specific element pertaining to the second island are moved.
The chromosome pertaining to the first island and the chromosome pertaining to the second island may be subjected to a genetic operation, i.e., crossover, in the first algorithm executing step, at the time of execution of the genetic algorithm; by extraction of a region including a specific element from the chromosome pertaining to either the first or second island; by reading the thus-extracted region a counterpart region of the chromosome pertaining to the other island; and by inserting the region into the other island.
Therefore, by means of the foregoing configuration, in the first algorithm executing step, a first island and a second island can also be used at the time of execution of the genetic algorithm; the first island comprising a chromosome group (population) including a plurality of vertically-split sub-divided regions; and the second island comprising a chromosome group including a plurality of horizontally-split sub-divided regions. Therefore, the diversity of the chromosomes which are included in the chromosome group and act as candidate solutions for solution can be maintained, and efficient retrieval of an optimum solution and efficient reduction of non-uniformity in density of elements can be effected.